/**
 * 面试题22相关题目：链表的中间节点
 * <p>
 * 如果节点总数为奇数，则返回中间节点；如果节点总数为偶数，则返回中间两个节点的任意一个
 */
public class Offer_22_II {
    /**
     * 快慢指针
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        // 快慢指针
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            // 快指针走两步
            fast = fast.next.next;
            // 慢指针走一步
            slow = slow.next;
        }
        // fast 到达末尾时，slow 正好在中间
        return slow;
    }

    public static void main(String[] args) {
        // 构造链表
        // 虚拟头节点
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        for (int i = 1; i <= 10; i++) {
            cur.next = new ListNode();
            cur.next.val = i;
            cur = cur.next;
        }
        // 打印链表
        cur = dummyHead;
        printListNode(cur.next);

        // 获取链表的中间节点
        Offer_22_II solution = new Offer_22_II();
        ListNode ans = solution.middleNode(dummyHead.next);
        // 打印结果
        printListNode(ans);
    }

    public static void printListNode(ListNode node) {
        System.out.print("[");
        while (node != null) {
            System.out.print(node.val + " -> ");
            node = node.next;
        }
        System.out.println("null]");
    }
}
